InforLorV4, Main, Exploration, bibRecord, 001E89

SCHEDULING IN THE PRESENCE OF PROCESSOR NETWORKS: COMPLEXITY AND APPROXIMATION

Identifieur interne : 001E89 ( Main/Exploration ); précédent : 001E88; suivant : 001E90

SCHEDULING IN THE PRESENCE OF PROCESSOR NETWORKS: COMPLEXITY AND APPROXIMATION

Auteurs : Vincent Boudht [France] ; Johanne Cohhn [France] ; Rodolphe Giroudeau [France] ; Jean-Clalide Könic [France]

Source :

RAIRO. Recherche opérationnelle [ 0399-0559 ] ; 2012.

RBID : Pascal:12-0251183

Descripteurs français

Pascal (Inist)
- Temps total achèvement, Minimisation, Temps polynomial, Problème NP complet, Topologie circuit, Système réparti, Anneau, Graphe précédence, Contrainte précédence, Graphe biparti, Multiprocesseur, Algorithme approximation, Délai transmission, Modélisation, ., Ordonnancement processeur.

English descriptors

KwdEn :
- Approximation algorithm, Bipartite graph, Distributed system, Makespan, Minimization, Modeling, Multiprocessor, NP complete problem, Network topology, Polynomial time, Precedence constraint, Precedence graph, Processor scheduling, Ring, Transmission time.

Abstract

In this paper, we study the problem of makespan minimization for the multiprocessor scheduling problem in the presence of communication delays. The communication delay between two tasks i and j depends on the distance between the two processors on which these two tasks are executed. Lahlou shows that a simple polynomial-time algorithm exists when the length of the schedule is at most two (the problem becomes NP-complete when the length of the schedule is at most three). We prove that there is no polynomial-time algorithm with a performance guarantee of less than 4/3 (unless P = NP) to minimize the makespan when the network topology is a chain or ring and the precedence graph is a bipartite graph of depth one. We also develop two polynomial-time approximation algorithms with constant ratio dedicated to cases where the processor network admits a limited or unlimited number of processors.

Affiliations:

Links toward previous steps (curation, corpus...)

to stream PascalFrancis, to step Corpus: 000118
to stream PascalFrancis, to step Curation: 000894
to stream PascalFrancis, to step Checkpoint: 000102
to stream Main, to step Merge: 001F11
to stream Main, to step Curation: 001E89

Le document en format XML

<record><TEI><teiHeader><fileDesc><titleStmt><title xml:lang="en" level="a">SCHEDULING IN THE PRESENCE OF PROCESSOR NETWORKS: COMPLEXITY AND APPROXIMATION</title>
<author><name sortKey="Boudht, Vincent" sort="Boudht, Vincent" uniqKey="Boudht V" first="Vincent" last="Boudht">Vincent Boudht</name>
<affiliation wicri:level="3"><inist:fA14 i1="01"><s1>LIRMM, 161 rue Ada, 34392 Mtoutpellier Cedex 5</s1>
<s2>UMR 5055</s2>
<s3>FRA</s3>
<sZ>1 aut.</sZ>
<sZ>3 aut.</sZ>
<sZ>4 aut.</sZ>
</inist:fA14>
<country>France</country>
<wicri:noRegion>UMR 5055</wicri:noRegion>
<placeName><region type="region" nuts="2">Occitanie (région administrative)</region>
<region type="old region" nuts="2">Languedoc-Roussillon</region>
<settlement type="city">Mtoutpellier</settlement>
</placeName>
</affiliation>
</author>
<author><name sortKey="Cohhn, Johanne" sort="Cohhn, Johanne" uniqKey="Cohhn J" first="Johanne" last="Cohhn">Johanne Cohhn</name>
<affiliation wicri:level="3"><inist:fA14 i1="02"><s1>LORIA</s1>
<s2>54506 Vandoeuvre-lès-Nancy</s2>
<s3>FRA</s3>
<sZ>2 aut.</sZ>
</inist:fA14>
<country>France</country>
<placeName><region type="region" nuts="2">Grand Est</region>
<region type="old region" nuts="2">Lorraine (région)</region>
<settlement type="city">Vandœuvre-lès-Nancy</settlement>
</placeName>
</affiliation>
</author>
<author><name sortKey="Giroudeau, Rodolphe" sort="Giroudeau, Rodolphe" uniqKey="Giroudeau R" first="Rodolphe" last="Giroudeau">Rodolphe Giroudeau</name>
<affiliation wicri:level="3"><inist:fA14 i1="01"><s1>LIRMM, 161 rue Ada, 34392 Mtoutpellier Cedex 5</s1>
<s2>UMR 5055</s2>
<s3>FRA</s3>
<sZ>1 aut.</sZ>
<sZ>3 aut.</sZ>
<sZ>4 aut.</sZ>
</inist:fA14>
<country>France</country>
<wicri:noRegion>UMR 5055</wicri:noRegion>
<placeName><region type="region" nuts="2">Occitanie (région administrative)</region>
<region type="old region" nuts="2">Languedoc-Roussillon</region>
<settlement type="city">Mtoutpellier</settlement>
</placeName>
</affiliation>
</author>
<author><name sortKey="Konic, Jean Clalide" sort="Konic, Jean Clalide" uniqKey="Konic J" first="Jean-Clalide" last="Könic">Jean-Clalide Könic</name>
<affiliation wicri:level="3"><inist:fA14 i1="01"><s1>LIRMM, 161 rue Ada, 34392 Mtoutpellier Cedex 5</s1>
<s2>UMR 5055</s2>
<s3>FRA</s3>
<sZ>1 aut.</sZ>
<sZ>3 aut.</sZ>
<sZ>4 aut.</sZ>
</inist:fA14>
<country>France</country>
<wicri:noRegion>UMR 5055</wicri:noRegion>
<placeName><region type="region" nuts="2">Occitanie (région administrative)</region>
<region type="old region" nuts="2">Languedoc-Roussillon</region>
<settlement type="city">Mtoutpellier</settlement>
</placeName>
</affiliation>
</author>
</titleStmt>
<publicationStmt><idno type="wicri:source">INIST</idno>
<idno type="inist">12-0251183</idno>
<date when="2012">2012</date>
<idno type="stanalyst">PASCAL 12-0251183 INIST</idno>
<idno type="RBID">Pascal:12-0251183</idno>
<idno type="wicri:Area/PascalFrancis/Corpus">000118</idno>
<idno type="wicri:Area/PascalFrancis/Curation">000894</idno>
<idno type="wicri:Area/PascalFrancis/Checkpoint">000102</idno>
<idno type="wicri:explorRef" wicri:stream="PascalFrancis" wicri:step="Checkpoint">000102</idno>
<idno type="wicri:doubleKey">0399-0559:2012:Boudht V:scheduling:in:the</idno>
<idno type="wicri:Area/Main/Merge">001F11</idno>
<idno type="wicri:Area/Main/Curation">001E89</idno>
<idno type="wicri:Area/Main/Exploration">001E89</idno>
</publicationStmt>
<sourceDesc><biblStruct><analytic><title xml:lang="en" level="a">SCHEDULING IN THE PRESENCE OF PROCESSOR NETWORKS: COMPLEXITY AND APPROXIMATION</title>
<author><name sortKey="Boudht, Vincent" sort="Boudht, Vincent" uniqKey="Boudht V" first="Vincent" last="Boudht">Vincent Boudht</name>
<affiliation wicri:level="3"><inist:fA14 i1="01"><s1>LIRMM, 161 rue Ada, 34392 Mtoutpellier Cedex 5</s1>
<s2>UMR 5055</s2>
<s3>FRA</s3>
<sZ>1 aut.</sZ>
<sZ>3 aut.</sZ>
<sZ>4 aut.</sZ>
</inist:fA14>
<country>France</country>
<wicri:noRegion>UMR 5055</wicri:noRegion>
<placeName><region type="region" nuts="2">Occitanie (région administrative)</region>
<region type="old region" nuts="2">Languedoc-Roussillon</region>
<settlement type="city">Mtoutpellier</settlement>
</placeName>
</affiliation>
</author>
<author><name sortKey="Cohhn, Johanne" sort="Cohhn, Johanne" uniqKey="Cohhn J" first="Johanne" last="Cohhn">Johanne Cohhn</name>
<affiliation wicri:level="3"><inist:fA14 i1="02"><s1>LORIA</s1>
<s2>54506 Vandoeuvre-lès-Nancy</s2>
<s3>FRA</s3>
<sZ>2 aut.</sZ>
</inist:fA14>
<country>France</country>
<placeName><region type="region" nuts="2">Grand Est</region>
<region type="old region" nuts="2">Lorraine (région)</region>
<settlement type="city">Vandœuvre-lès-Nancy</settlement>
</placeName>
</affiliation>
</author>
<author><name sortKey="Giroudeau, Rodolphe" sort="Giroudeau, Rodolphe" uniqKey="Giroudeau R" first="Rodolphe" last="Giroudeau">Rodolphe Giroudeau</name>
<affiliation wicri:level="3"><inist:fA14 i1="01"><s1>LIRMM, 161 rue Ada, 34392 Mtoutpellier Cedex 5</s1>
<s2>UMR 5055</s2>
<s3>FRA</s3>
<sZ>1 aut.</sZ>
<sZ>3 aut.</sZ>
<sZ>4 aut.</sZ>
</inist:fA14>
<country>France</country>
<wicri:noRegion>UMR 5055</wicri:noRegion>
<placeName><region type="region" nuts="2">Occitanie (région administrative)</region>
<region type="old region" nuts="2">Languedoc-Roussillon</region>
<settlement type="city">Mtoutpellier</settlement>
</placeName>
</affiliation>
</author>
<author><name sortKey="Konic, Jean Clalide" sort="Konic, Jean Clalide" uniqKey="Konic J" first="Jean-Clalide" last="Könic">Jean-Clalide Könic</name>
<affiliation wicri:level="3"><inist:fA14 i1="01"><s1>LIRMM, 161 rue Ada, 34392 Mtoutpellier Cedex 5</s1>
<s2>UMR 5055</s2>
<s3>FRA</s3>
<sZ>1 aut.</sZ>
<sZ>3 aut.</sZ>
<sZ>4 aut.</sZ>
</inist:fA14>
<country>France</country>
<wicri:noRegion>UMR 5055</wicri:noRegion>
<placeName><region type="region" nuts="2">Occitanie (région administrative)</region>
<region type="old region" nuts="2">Languedoc-Roussillon</region>
<settlement type="city">Mtoutpellier</settlement>
</placeName>
</affiliation>
</author>
</analytic>
<series><title level="j" type="main">RAIRO. Recherche opérationnelle</title>
<title level="j" type="abbreviated">RAIRO, Rech. opér.</title>
<idno type="ISSN">0399-0559</idno>
<imprint><date when="2012">2012</date>
</imprint>
</series>
</biblStruct>
</sourceDesc>
<seriesStmt><title level="j" type="main">RAIRO. Recherche opérationnelle</title>
<title level="j" type="abbreviated">RAIRO, Rech. opér.</title>
<idno type="ISSN">0399-0559</idno>
</seriesStmt>
</fileDesc>
<profileDesc><textClass><keywords scheme="KwdEn" xml:lang="en"><term>Approximation algorithm</term>
<term>Bipartite graph</term>
<term>Distributed system</term>
<term>Makespan</term>
<term>Minimization</term>
<term>Modeling</term>
<term>Multiprocessor</term>
<term>NP complete problem</term>
<term>Network topology</term>
<term>Polynomial time</term>
<term>Precedence constraint</term>
<term>Precedence graph</term>
<term>Processor scheduling</term>
<term>Ring</term>
<term>Transmission time</term>
</keywords>
<keywords scheme="Pascal" xml:lang="fr"><term>Temps total achèvement</term>
<term>Minimisation</term>
<term>Temps polynomial</term>
<term>Problème NP complet</term>
<term>Topologie circuit</term>
<term>Système réparti</term>
<term>Anneau</term>
<term>Graphe précédence</term>
<term>Contrainte précédence</term>
<term>Graphe biparti</term>
<term>Multiprocesseur</term>
<term>Algorithme approximation</term>
<term>Délai transmission</term>
<term>Modélisation</term>
<term>.</term>
<term>Ordonnancement processeur</term>
</keywords>
</textClass>
</profileDesc>
</teiHeader>
<front><div type="abstract" xml:lang="en">In this paper, we study the problem of makespan minimization for the multiprocessor scheduling problem in the presence of communication delays. The communication delay between two tasks i and j depends on the distance between the two processors on which these two tasks are executed. Lahlou shows that a simple polynomial-time algorithm exists when the length of the schedule is at most two (the problem becomes NP-complete when the length of the schedule is at most three). We prove that there is no polynomial-time algorithm with a performance guarantee of less than 4/3 (unless P = NP) to minimize the makespan when the network topology is a chain or ring and the precedence graph is a bipartite graph of depth one. We also develop two polynomial-time approximation algorithms with constant ratio dedicated to cases where the processor network admits a limited or unlimited number of processors.</div>
</front>
</TEI>
<affiliations><list><country><li>France</li>
</country>
<region><li>Grand Est</li>
<li>Languedoc-Roussillon</li>
<li>Lorraine (région)</li>
<li>Occitanie (région administrative)</li>
</region>
<settlement><li>Mtoutpellier</li>
<li>Vandœuvre-lès-Nancy</li>
</settlement>
</list>
<tree><country name="France"><region name="Occitanie (région administrative)"><name sortKey="Boudht, Vincent" sort="Boudht, Vincent" uniqKey="Boudht V" first="Vincent" last="Boudht">Vincent Boudht</name>
</region>
<name sortKey="Cohhn, Johanne" sort="Cohhn, Johanne" uniqKey="Cohhn J" first="Johanne" last="Cohhn">Johanne Cohhn</name>
<name sortKey="Giroudeau, Rodolphe" sort="Giroudeau, Rodolphe" uniqKey="Giroudeau R" first="Rodolphe" last="Giroudeau">Rodolphe Giroudeau</name>
<name sortKey="Konic, Jean Clalide" sort="Konic, Jean Clalide" uniqKey="Konic J" first="Jean-Clalide" last="Könic">Jean-Clalide Könic</name>
</country>
</tree>
</affiliations>
</record>

Pour manipuler ce document sous Unix (Dilib)

EXPLOR_STEP=$WICRI_ROOT/Wicri/Lorraine/explor/InforLorV4/Data/Main/Exploration

HfdSelect -h $EXPLOR_STEP/biblio.hfd -nk 001E89 | SxmlIndent | more

HfdSelect -h $EXPLOR_AREA/Data/Main/Exploration/biblio.hfd -nk 001E89 | SxmlIndent | more

Pour mettre un lien sur cette page dans le réseau Wicri

{{Explor lien
   |wiki=    Wicri/Lorraine
   |area=    InforLorV4
   |flux=    Main
   |étape=   Exploration
   |type=    RBID
   |clé=     Pascal:12-0251183
   |texte=   SCHEDULING IN THE PRESENCE OF PROCESSOR NETWORKS: COMPLEXITY AND APPROXIMATION
}}

This area was generated with Dilib version V0.6.33.
Data generation: Mon Jun 10 21:56:28 2019. Site generation: Fri Feb 25 15:29:27 2022

	Serveur d'exploration sur la recherche en informatique en Lorraine
	Attention, ce site est en cours de développement ! Attention, site généré par des moyens informatiques à partir de corpus bruts. Les informations ne sont donc pas validées.

Serveur d'exploration sur la recherche en informatique en Lorraine

SCHEDULING IN THE PRESENCE OF PROCESSOR NETWORKS: COMPLEXITY AND APPROXIMATION

SCHEDULING IN THE PRESENCE OF PROCESSOR NETWORKS: COMPLEXITY AND APPROXIMATION

Source :

Descripteurs français

English descriptors

Abstract

Links toward previous steps (curation, corpus...)

Le document en format XML

Pour manipuler ce document sous Unix (Dilib)

Pour mettre un lien sur cette page dans le réseau Wicri